%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{A nonempty binary heap $T$, in sequence representation, having
  $n$ internal vertices. An element $v$ that is to be inserted as a
  new internal vertex of $T$.}
%%
%% output
\KwOut{The binary heap $T$ augmented with the new internal vertex $v$.}
\BlankLine
%%
%% algorithm body
$i \assign n$\;
\While{$i > 0$}{
  $p \assign \lfloor (i - 1) / 2 \rfloor$\;
  \If{$\kappa_{T[p]} \leq \kappa_{v}$}{
    exit the loop\;
  }
  \Else{
    $T[i] \assign T[p]$\;
    $i \assign p$\;
  }
}
$T[i] \assign v$\;
\Return $T$\;
